package redBlackTree;

import java.util.HashSet;
import java.util.Set;

//RedBlackTree class
//
// CONSTRUCTION: with a negative infinity sentinel
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print all items
// ******************ERRORS********************************
// Exceptions are thrown by insert if warranted and remove.

/**
 * Implements a red-black tree. Note that all "matching" is based on the
 * compareTo method.
 * 
 * @author Mark Allen Weiss
 */

@SuppressWarnings("unchecked")
public class RedBlackTree<T extends Comparable<T>>
{
	/**
	 * Construct the tree.
	 */
	@SuppressWarnings("unchecked")
	public RedBlackTree()
	{
		this.header = new RedBlackNode<T>(null);
		this.header.left = this.header.right = RedBlackTree.nullNode;
	}

	/**
	 * Compare item and t.element, using compareTo, with caveat that if t is
	 * header, then item is always larger. This routine is called if is possible
	 * that t is header. If it is not possible for t to be header, use compareTo
	 * directly.
	 */
	@SuppressWarnings("unchecked")
	private final int compare(Comparable<T> item, RedBlackNode<T> t)
	{
		if (t == this.header)
			return 1;
		else return item.compareTo(t.element);
	}

	/**
	 * Insert into the tree.
	 * 
	 * @param item
	 *            the item to insert.
	 * @throws DuplicateItemException
	 *             if item is already present.
	 */
	@SuppressWarnings("unchecked")
	public void insert(Comparable<T> item)
	{
		RedBlackTree.current = RedBlackTree.parent = RedBlackTree.grand = this.header;
		RedBlackTree.nullNode.element = item;

		while (this.compare(item, RedBlackTree.current) != 0)
		{
			RedBlackTree.great = RedBlackTree.grand;
			RedBlackTree.grand = RedBlackTree.parent;
			RedBlackTree.parent = RedBlackTree.current;
			RedBlackTree.current = this.compare(item, RedBlackTree.current) < 0 ? RedBlackTree.current.left
					: RedBlackTree.current.right;

			// Check if two red children; fix if so
			if (RedBlackTree.current.left.color == RedBlackTree.RED
					&& RedBlackTree.current.right.color == RedBlackTree.RED)
				this.handleReorient(item);
		}

		// Insertion fails if already present
		if (RedBlackTree.current != RedBlackTree.nullNode)
			throw new DuplicateItemException(item.toString());
		RedBlackTree.current = new RedBlackNode(item, RedBlackTree.nullNode,
				RedBlackTree.nullNode);

		// Attach to parent
		if (this.compare(item, RedBlackTree.parent) < 0)
			RedBlackTree.parent.left = RedBlackTree.current;
		else RedBlackTree.parent.right = RedBlackTree.current;
		this.handleReorient(item);
	}

	/**
	 * Remove from the tree.
	 * 
	 * @param x
	 *            the item to remove.
	 * @throws UnsupportedOperationException
	 *             if called.
	 */
	public void remove(Comparable<T> x)
	{
		throw new UnsupportedOperationException();
	}

	/**
	 * Find the smallest item the tree.
	 * 
	 * @return the smallest item or null if empty.
	 */
	public T findMin()
	{
		if (this.isEmpty())
			return null;

		RedBlackNode<T> itr = this.header.right;

		while (itr.left != RedBlackTree.nullNode)
			itr = itr.left;

		return itr.element;
	}

	/**
	 * Find the largest item in the tree.
	 * 
	 * @return the largest item or null if empty.
	 */
	public T findMax()
	{
		if (this.isEmpty())
			return null;

		RedBlackNode<T> itr = this.header.right;

		while (itr.right != RedBlackTree.nullNode)
			itr = itr.right;

		return itr.element;
	}

	/**
	 * Find an item in the tree.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item or null if not found.
	 */
	public T find(T x)
	{
		RedBlackTree.nullNode.element = x;
		RedBlackTree.current = this.header.right;

		for (;;)
		{
			if (x.compareTo((T) RedBlackTree.current.element) < 0)
				RedBlackTree.current = RedBlackTree.current.left;
			else if (x.compareTo((T) RedBlackTree.current.element) > 0)
				RedBlackTree.current = RedBlackTree.current.right;
			else if (RedBlackTree.current != RedBlackTree.nullNode)
				return (T) RedBlackTree.current.element;
			else return null;
		}
	}

	public Set<T> findRange(T min, T max)
	{
		Set<T> result = new HashSet<T>();
		this.findRange(this.header.right, min, max, result);
		return result;
	}

	private void findRange(RedBlackNode<T> node, T min, T max, Set<T> result)
	{
		if (node == RedBlackTree.nullNode)
		{
			return;
		}
		if (min.compareTo(node.element) > 0)
		{
			this.findRange(node.right, min, max, result);
		}
		else if (max.compareTo(node.element) < 0)
		{
			this.findRange(node.left, min, max, result);
		}
		else
		{
			result.add(node.element);
			this.findRange(node.right, min, max, result);
			this.findRange(node.left, min, max, result);
		}
	}

	/**
	 * Make the tree logically empty.
	 */
	@SuppressWarnings("unchecked")
	public void makeEmpty()
	{
		this.header.right = RedBlackTree.nullNode;
	}

	@Override
	public String toString()
	{
		return this.toString(this.header.right);
	}

	public String toString(RedBlackNode<T> t)
	{
		String s = "";
		if (t != RedBlackTree.nullNode)
		{
			s += this.toString(t.left);
			s += t.element + System.getProperty("line.separator");
			s += this.toString(t.right);
		}

		return s;
	}

	/**
	 * Print all items.
	 */
	public void printTree()
	{
		this.printTree(this.header.right);
	}

	/**
	 * Internal method to print a subtree in sorted order.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 */
	private void printTree(RedBlackNode<T> t)
	{
		if (t != RedBlackTree.nullNode)
		{
			this.printTree(t.left);
			// System.out.println(t.element);
			this.printTree(t.right);
		}
	}

	/**
	 * Test if the tree is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty()
	{
		return this.header.right == RedBlackTree.nullNode;
	}

	/**
	 * Internal routine that is called during an insertion if a node has two red
	 * children. Performs flip and rotations.
	 * 
	 * @param item
	 *            the item being inserted.
	 */
	@SuppressWarnings("unchecked")
	private void handleReorient(Comparable<T> item)
	{
		// Do the color flip
		RedBlackTree.current.color = RedBlackTree.RED;
		RedBlackTree.current.left.color = RedBlackTree.BLACK;
		RedBlackTree.current.right.color = RedBlackTree.BLACK;

		if (RedBlackTree.parent.color == RedBlackTree.RED) // Have to rotate
		{
			RedBlackTree.grand.color = RedBlackTree.RED;
			if ((this.compare(item, RedBlackTree.grand) < 0) != (this.compare(
					item, RedBlackTree.parent) < 0))
				RedBlackTree.parent = this.rotate(item, RedBlackTree.grand); // Start
			// dbl
			// rotate
			RedBlackTree.current = this.rotate(item, RedBlackTree.great);
			RedBlackTree.current.color = RedBlackTree.BLACK;
		}
		this.header.right.color = RedBlackTree.BLACK; // Make root black
	}

	/**
	 * Internal routine that performs a single or double rotation. Because the
	 * result is attached to the parent, there are four cases. Called by
	 * handleReorient.
	 * 
	 * @param item
	 *            the item in handleReorient.
	 * @param parent
	 *            the parent of the root of the rotated subtree.
	 * @return the root of the rotated subtree.
	 */
	@SuppressWarnings("unchecked")
	private RedBlackNode<T> rotate(Comparable<T> item, RedBlackNode<T> parent)
	{
		if (this.compare(item, parent) < 0)
			return parent.left = this.compare(item, parent.left) < 0 ? RedBlackTree
					.rotateWithLeftChild(parent.left)
					: // LL
					RedBlackTree.rotateWithRightChild(parent.left); // LR
		else return parent.right = this.compare(item, parent.right) < 0 ? RedBlackTree
				.rotateWithLeftChild(parent.right)
				: // RL
				RedBlackTree.rotateWithRightChild(parent.right); // RR
	}

	/**
	 * Rotate binary tree node with left child.
	 */
	private static RedBlackNode rotateWithLeftChild(RedBlackNode k2)
	{
		RedBlackNode k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		return k1;
	}

	/**
	 * Rotate binary tree node with right child.
	 */
	private static RedBlackNode rotateWithRightChild(RedBlackNode k1)
	{
		RedBlackNode k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		return k2;
	}

	private static class RedBlackNode<T extends Comparable<T>>
	{
		// Constructors
		RedBlackNode(T theElement)
		{
			this(theElement, null, null);
		}

		RedBlackNode(T theElement, RedBlackNode<T> lt, RedBlackNode<T> rt)
		{
			this.element = theElement;
			this.left = lt;
			this.right = rt;
			this.color = RedBlackTree.BLACK;
		}

		T				element;	// The data in the node
		RedBlackNode<T>	left;		// Left child
		RedBlackNode<T>	right;		// Right child
		int				color;		// Color
	}

	private final RedBlackNode<T>	header;
	private static RedBlackNode		nullNode;
	static
	// Static initializer for nullNode
	{
		RedBlackTree.nullNode = new RedBlackNode(null);
		RedBlackTree.nullNode.left = RedBlackTree.nullNode.right = RedBlackTree.nullNode;
	}

	private static final int		BLACK	= 1;	// Black must be 1
	private static final int		RED		= 0;

	// Used in insert routine and its helpers
	@SuppressWarnings("unchecked")
	private static RedBlackNode		current;
	@SuppressWarnings("unchecked")
	private static RedBlackNode		parent;
	@SuppressWarnings("unchecked")
	private static RedBlackNode		grand;
	@SuppressWarnings("unchecked")
	private static RedBlackNode		great;

}